МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» Кафедра САПР Звіт до лабораторної роботи №13 на тему «ДЕРЕВА І ГРАФИ В МОВІ ПРОГРАМУВАННЯ С» з курсу «Проблемно-орієнтовані мови програмування» ЛЬВІВ 2011 Мета роботи Навчитися використовувати логічну структуру дерев для програмування задач з використанням графів. Теоретичні відомості Дерева являють собою найбільш важливі нелінійні структури, що зустрічаються в обчислювальних алгоритмах. Існує кілька класів дерев, серед яких особливою "популярністю" користуються бінарні (двійкові) дерева. Вони застосовуються у різноманітних алгоритмах (програмах): наприклад, деякі компілятори з мов високого рівня використовують їх для аналізу й обчислення арифметичних виразів. Ще однією причиною популярності бінарних дерев є простота їхньої організації. Дерево - це неорієнтований зв'язний граф без циклів. Визначимо формальне дерево як скінченну множину Т, яка складається з одного або більше вузлів, таких, що: є один позначений вузол, який називається коренем даного дерева; інші вузли (крім кореня) містяться в m >= 0 множинах Т1, Т2, ..., Тm, які попарно не перетинаються, і кожна з яких у свою чергу є деревом. Дерева Т1, Т2, ..., Тm називаються піддеревами даного дерева. Це визначення є рекурсивним, тобто воно визначає дерево в термінах самих же дерев. З нього слідує, що кожний вузол дерева є коренем деякого піддерева, що міститься в цьому дереві. Число таких піддерев у даному вузлі називають його ступенем. В бінарних деревах є також листя. Це вузли з нульовим степенем. Всі інші (некінцеві) вузли називають вузлами розгалуження. Корінь - це такий вузол, з якого йдуть зв'язки до всіх інших элементів дерева. Дерева на папері зображують так: спочатку малюють корінь, потім від нього малюють зв’язки до вузлів-нащадків, від них зв'язки до їхніх нащадків і т. д. Ще однією характеристикою дерева є його висота. Це шлях максимальної довжини від листка до кореня. У бінарному дереві кожний вузол має тільки два піддерева. У кожного вузла є ліве й праве піддерево. Вузол і його піддерева називають взагалі по-різному, наприклад: батько, син і брат; або: батько з "лівим" і "правим" синами. Більш формально бінарне дерево можна визначити як скінченну множину вузлів, яка або пуста, або складається з кореня з одним/двома бінарними деревами, що не перетинаються. На мові С вузол бінарного дерева можна описати у вигляді наступної структури: struct node { іnt key; // Ключ ... // Дані struct node *left; // Посилання на ліве пiддерево/вузол struct node *rіght; // Посилання на праве пiддерево/вузол }; Для обходу дерева використовують ключі. Ключ - спеціальна змінна, яка полегшує доступ до вузлів дерева. Звичайно, це ціле число, що зберігається в кожному вузлі дерева і задовольняює деяким умовам. Наприклад, таким: нехай всі ключі в лівому піддереві поточного вузла менші ключа в ньому, а всі ключі в правому піддереві - більші або рівні поточному. При роботі з бінарними деревами потрібно вміти додати, видалити, знайти в них вузол з необхідною інформацією, або створити довільне дерево. Однією з головних причин, що лежать в основі появи мов програмування високого рівня, є завдання, що вимагають великих обсягів обчислень. Тому до мов програмування ставляться вимоги максимального наближення форми запису обчислень до природної мови математики. У цьому зв'язку однією з перших областей системного програмування сформувалося дослідження способів трансляції виразів. Тут отримані численні результати, однак найбільше поширення одержав метод трансляції за допомогою зворотного польського запису, що запропонував польський математик Я. Лукашевич. Нехай задано простий арифметичний вираз:
. (1) Представимо цей вираз у вигляді...